﻿#ifndef __L5_GRAPH_H_INCL__
#define __L5_GRAPH_H_INCL__

#include<iostream>
#include<map>
#include<list>
#include<vector>

using namespace std;

const int MAXVERTICES = 50;	     //最大顶点数
const int MAXEdgeS = 50;	       //最大边数

typedef struct {
  int v1;
  int v2;
} EDGE_STRU;                     //保存边的顶点


class L5_Graph {
 public:
  L5_Graph();
  virtual ~L5_Graph();

  bool InsertEdge(int v1, int v2, int edgeno);    //插入一条边(v1到v2,边的名称为edgeno)
  bool DeleteEdge(int v1, int v2, int edgeno);    //删除一条边(v1到v2,边的名称为edgeno)

  bool InsertVertex(int v);			                  //插入一个名为v的顶点（与任何顶点不邻接）
  bool DeleteVertex(int v);			                  //删除与顶点V关联的所有边

  map <int, EDGE_STRU> edge_map;		              //key:边的标示,value:边对应的顶点

  void printMatrixA();                            //打印关联矩阵
  void printMatrixX();                            //打印邻接矩阵
  void printMatrixC();                            //打印全连通矩阵

  bool MatrixA[MAXVERTICES][MAXEdgeS];            //保存关联矩阵
  bool MatrixX[MAXVERTICES][MAXVERTICES];         //保存邻接矩阵
  bool MatrixC[MAXVERTICES][MAXVERTICES];         //保存全连通矩阵
  list<int > vertex;  //顶点表


 protected:
  //int numedge;            //边的数量
  //int numVertices;        //顶点的数量


 private:
  bool _vertex_order;       //vertex中是否排序，ture为已排序,false为未排序
  bool model_change_flag;   //模型改变标志，如果模型发生改变则置true.生成关联矩阵后置false
  bool matrixa_change_flag; //是否需重新生成关联矩阵，如果关联矩阵改变则置true。重生成邻接矩阵后置否
  vector<int> _vertex_list; //根据顶点表 vertex 的各元素顺序将各元素存在vector中，实现随机访问
  bool MatrixT[MAXVERTICES][MAXVERTICES];   //临时

  void GenMatrixA();        //生成关联矩阵
  void GenMatrixX();        //生成邻接矩阵
  void GenMatrixC();        //生成全连通矩阵
};

//补充
inline L5_Graph::L5_Graph(){
  _vertex_order = false;
  model_change_flag = true;
  matrixa_change_flag = true;
  _vertex_list.clear();

}

// Destructor implementation
inline L5_Graph::~L5_Graph(){
}

//插入一条边
bool L5_Graph::InsertEdge(int v1, int v2, int edgeno){
  EDGE_STRU edge = {v1, v2};
  edge_map.insert(map<int, EDGE_STRU>::value_type(edgeno, edge) ); //待补充，错误处理
  model_change_flag = true;   //模型改变
  return 0;
}

//删除一条边
bool L5_Graph::DeleteEdge(int v1, int v2, int edgeno){
  edge_map.erase(edgeno);    //待补充，删除成功与否标志
  model_change_flag = true;   //模型改变
  return 0;
}

//插入一个顶点
bool L5_Graph::InsertVertex(int v){
  vertex.push_back(v);        //需补充，判错
  _vertex_order = false;      //顶点顺序改变
  model_change_flag = true;   //模型改变
  return 0;
}

//删除顶点v及其关联的边
bool L5_Graph::DeleteVertex(int v){
  //遍历edge_map，查找并删除与顶点v关联的边
  for (map<int, EDGE_STRU>::iterator iter = edge_map.begin();
        iter != edge_map.end(); iter++ ) {
    if (iter->second.v1 == v || iter->second.v2 == v) {
      edge_map.erase(iter--);
    }
  }

  vertex.remove(v);     //在顶点表里将顶点v删除

  _vertex_order = false;      //顶点顺序改变
  model_change_flag = true;   //模型改变

  return 0;
}

//生成关联矩阵
void L5_Graph::GenMatrixA(){
  //判断模型是否改变过，如果改变则重新生成关联矩阵
  if (model_change_flag ) {
    //判断顶点表是否需排序
    if (!_vertex_order) {
      vertex.sort();      //如果顶点表没有排序，则按升序排序
      _vertex_order = true;

    }

    int i,j;

    //将关联矩阵所有元素置0
    for (i = 0; i < MAXVERTICES; i++ ) {
      for (j = 0; j < MAXEdgeS; j++ ) {
        MatrixA[i][j] = 0;
      }
    }

    //根据 vertex 和 edge_map 生成关联矩阵，
    j = 0;
    for (map<int, EDGE_STRU>::iterator iter = edge_map.begin(); iter != edge_map.end(); iter++) {

      i = 0;
      for (list<int>::iterator it = vertex.begin(); it != vertex.end(); it++) {
        if (*it == iter->second.v1) {
          MatrixA[i][j] = 1;
          break;
        }
        i++;
      }

      i = 0;
      for (list<int>::iterator it = vertex.begin(); it != vertex.end(); it++) {
        if (*it == iter->second.v2) {
          MatrixA[i][j] = 1;
          break;
        }
        i++;
      }

    j++;
    }

    model_change_flag = false;    //已生成新的关联矩阵
    matrixa_change_flag = true;   //关联矩阵已发生改变
  }
}

//生成邻接矩阵
void L5_Graph::GenMatrixX(){
  //判断模型是否发生改变，如改变则重新生成邻接矩阵
  GenMatrixA();     //生成关联矩阵

  if (matrixa_change_flag) {

    //初始化，将邻接矩阵所有元素置0
    for (int i = 0; i < MAXVERTICES; i++ ) {
      for (int j = 0; j < MAXVERTICES; j++ ) {
        MatrixX[i][j] = 0;
      }
    }

    //根据关联矩阵生成邻接矩阵
    for (int j = 0; j < edge_map.size(); j++ ) {//遍历关联矩阵每一列
      bool flag = false;           //是否找到该列第一个非零值，false表示未找到非零元素
      int row_temp;                //储存该列第一个非零元素所在行

      for (int i = 0; i < vertex.size(); i++ ) {//遍历关联矩阵每一行

        if (MatrixA[i][j] == 1) {
          if (!flag) {
            row_temp = i;
            flag = true;
          }
          else{
            MatrixX[row_temp][i] = 1;
            MatrixX[i][row_temp] = 1;
            break;
          }
        } //if end

      }//for end

    }//for end
    matrixa_change_flag = false;    //已重新生成邻接矩阵
  }
}

//打印关联矩阵
void L5_Graph::printMatrixA(){
  GenMatrixA();
  cout << "关联矩阵为:" << endl;
  //输出邻接矩阵的列对应的边
  for (map<int, EDGE_STRU>::iterator iter = edge_map.begin(); iter != edge_map.end(); iter++) {
    cout << '\t' << "(" << iter->first << ")";
  }
  cout << endl << "——————————————————————" << endl;

  _vertex_list.assign(vertex.begin(), vertex.end() );     //将vertex的元素复制到_vertex_list中，实现随机访问
  for (int i = 0; i < vertex.size(); i++) {
    cout << _vertex_list[i] << "|" << '\t';    //输出行对应的顶点
    for (int j = 0; j < edge_map.size(); j++) {
      cout << MatrixA[i][j] << '\t';
      }
    cout << endl;
    }
}

//打印邻接矩阵
void L5_Graph::printMatrixX(){
  GenMatrixX();
  _vertex_list.assign(vertex.begin(), vertex.end() );     //将vertex的元素复制到_vertex_list中，实现随机访问
  cout << "邻接矩阵为:" << endl;
  //输出邻接矩阵列对应的顶点
  for (int i = 0; i < vertex.size(); i++){
    cout << '\t' << _vertex_list[i];
  }
  cout << endl << "——————————————————————" << endl;

  for (int i = 0; i < vertex.size(); i++) {
    cout << _vertex_list[i] << "|" << '\t';    //输出行对应的顶点
    for (int j = 0; j < vertex.size(); j++) {
      cout << MatrixX[i][j] << '\t';
    }
    cout << endl;
  }

}


//生成全连通矩阵
void L5_Graph::GenMatrixC(){
  GenMatrixX();

  //初始化全连通矩阵
  for (int i = 0; i < vertex.size(); i++){
    for (int j = 0; j < vertex.size(); j++){
      if (i == j)
        MatrixC[i][j] = 1;
      else
        MatrixC[i][j] = 0;
    }
  }

  //
  for (int n = 0; n < vertex.size() - 1; n++){
    for (int i = 0; i < vertex.size(); i++){
      for (int j = 0; j < vertex.size(); j++){
        MatrixT[i][j] = MatrixC[i][j];
      }
    }

    for (int i = 0; i < vertex.size(); i++){
      for (int j = 0; j < vertex.size(); j++){
        for (int k = 0; k < vertex.size(); k++) {
          MatrixC[i][j] =  MatrixT[i][j] || (MatrixT[i][k]&& MatrixX[k][j]);
          if (MatrixC[i][j] )
            break;
        }
      }
    }
  }


}

//打印全连通矩阵
void L5_Graph::printMatrixC(){
  GenMatrixC();
  _vertex_list.assign(vertex.begin(), vertex.end() );     //将vertex的元素复制到_vertex_list中，实现随机访问
  cout << "全连通矩阵为:" << endl;
  for (int i = 0; i < vertex.size(); i++){
    cout << '\t' << _vertex_list[i];
  }
  cout << endl << "——————————————————————" << endl;
  for (int i = 0; i < vertex.size(); i++){
    cout << _vertex_list[i] << "|" << '\t';    //输出行对应的顶点
    for (int j = 0; j < vertex.size(); j++){
      cout << MatrixC[i][j] << '\t';
    }
    cout << endl;
  }

}



#endif // __L5_GRAPH_H_INCL__
